GreenRoute Ballari: A Hybrid Approach for Optimizing Waste Collection Routes Using K-Means Clustering and Genetic Algorithm

Abstract

The exponential growth of the population in Ballari has exacerbated the challenge of municipal waste management, necessitating the development of efficient waste collection strategies to address environmental and social concerns. In response to that our system introduces a hybrid approach that employs K-means clustering and Genetic Algorithm, for optimizing waste collection routes tailored to the unique waste generation profiles of the region. By utilizing Geographic Information System (GIS) data that is in the form of GeoJSON files containing the spatial distribution of waste collection points, we propose a methodology that combines K-means clustering and Genetic Algorithm to develop intelligent and fuel-efficient routes. Our system not only benefits municipal authorities in resource deployment and planning but also aids waste carrier vehicle drivers in prioritizing routes. Our findings contribute to the transformation of Ballari City towards eco-friendly and smart urban development.

Introduction

I. INTRODUCTION

The ever-growing problem of waste generation, particularly plastic waste, poses a significant environmental and economic threat to Ballari, Karnataka, as it does in many urban centers worldwide. Traditional methods often rely on static routes, leading to inefficiencies such as unnecessary travel distances, increased fuel consumption, and higher operational costs [4]. While GIS-based route optimization offers promise [2], a deeper understanding of how factors like waste composition, collection frequency, and truck design interact with each other is essential for even greater optimization [3, 5]. The GreenRoute Ballari proposes a novel system to address these challenges by leveraging machine learning and advanced route optimization techniques. This approach builds upon existing research on factors affecting route optimization. Unlike traditional methods that rely on static data, our system utilizes machine learning to predict waste volume and composition at collection points dynamically. This allows for a more data-driven and adaptable approach to route planning, similar to the work by Sutana (2021) who emphasizes the importance of dynamic factors in waste management systems [1]. As of March 2023, the Ballari City Corporation has 39 wards. 600 Pourakarmikas work day and night to make Ballari clean. Each ward is assigned nearly 2 vehicles if the ward is small, else 3-4 vehicles if the ward is huge. Large 12-ton vehicles carry the collected waste out of the city from the collection point near Stadium Road in the city. These large vehicles make 2-3 trips daily to dump all the waste, as Ballari daily puts up nearly 180 tonnes of waste.

A. Green Route Ballari factors in these Specifics, Including

1. Limited Vehicle Availability: The system considers the number of collection vehicles available in each ward (2-4).
2. Dynamic Waste Prediction: Machine learning algorithms predict waste volume and composition for each collection point, optimizing routes based on real-time data.
3. Time Window Constraints: The system accounts for designated collection times in each ward to ensure efficient scheduling.
4. Unique Traffic Patterns and Road Conditions: GreenRoute Ballari incorporates Ballari's unique traffic patterns and road conditions to optimize routes for faster collection times.

B. By optimizing routes based on these factors, Green Route Ballari aims to achieve significant benefits for Ballari

1. Reduced Fuel Consumption: Optimized routes minimize travel distances, leading to substantial fuel cost savings for the Ballari Municipal Corporation or private waste collection companies.
2. Improved Operational Efficiency: More efficient routes allow for faster collection times and better utilization of collection vehicles, reducing overall operational costs.
3. Environmental Sustainability: Reduced fuel consumption translates to lower greenhouse gas emissions, contributing to a cleaner Ballari.
4. Unlocking Economic Opportunities: By accurately predicting waste composition, Green Route Ballari can help identify waste segregation and resource recovery opportunities, particularly valuable wet waste that can benefit farmers.

C. The GreenRoute Ballari system Caters to a Diverse Audience within the waste Collection Management Ecosystem

1. Waste Management Authorities: Gain real-time data and insights to optimize waste collection strategies and ensure regulatory compliance.
2. Fleet Managers: Utilize the system to monitor and manage the waste collection fleet, optimize routes, and schedule vehicle maintenance.
3. Waste Collection Drivers: Receive optimized routes through a user-friendly interface, facilitating navigation and communication with the system.
4. System Administrators: Maintain the system, manage user access, and troubleshoot any technical issues.
5. Government Officials: Leverage data-driven insights for informed decision-making regarding waste management policies and resource allocation.

D. GreenRoute Ballari's key Features Include

1. Data Storage and Analysis: Stores and analyses historical and real-time data to generate route optimization strategies and operational insights.
2. Machine Learning for Waste Prediction: Employs machine learning algorithms to predict waste volume and composition at collection points, enabling dynamic route planning.
3. Genetic Algorithm for Route Optimization: Utilizes a GA to optimize waste collection routes based on dynamic waste prediction and collection point data.
4. Mapping Integration: Optimized routes are visually displayed to drivers through integration with mapping services like MapBox API, aiding navigation.
5. User Interface: User-friendly interfaces for municipal administrators and drivers display optimized routes, collection points, and real-time updates.
6. Security Measures: Secure communication protocols ensure the confidentiality of route information sent to drivers.

By implementing the GreenRoute Ballari project, Ballari can move towards a more efficient, cost-effective, and sustainable waste management system, paving the way for a cleaner, healthier, and more resource-conscious future.

II. LITERATURE REVIEW

III. METHODOLOGY

This section presents a methodology for optimizing waste collection routes in Ballari City using a combination of K-means clustering and Genetic Algorithm. The main aim of the system is to optimize the total distance traveled by waste collection vehicles while considering capacity constraints. Initially, the system utilizes Geographic Information System (GIS) data that is in the form of GeoJSON files containing the spatial distribution of waste collection points. Further, K-Means Clustering is employed to group these points into clusters, representing potential stops for waste collection vehicles. Subsequently, the Genetic Algorithm is applied to generate optimized routes for waste collection vehicles within each cluster, by considering vehicle capacity limitations. The proposed methodology aims to improve the effectiveness of waste collection operations, leading to improved resource utilization, reduced fuel consumption, and lower emissions.

A. Data Collection and Clustering Using K-Means Clustering Algorithm

The input data consists of spatial information about waste generation zones, including zone identifiers, zone names, population, and waste generation volumes. To prepare the data for route optimization, the coordinates of waste generation zones are extracted from the GeoJSON files. K-Means Clustering is then applied to group these coordinates into clusters, each representing a potential stop for waste collection vehicles. Here, the predetermined number of clusters is based on the availability of waste collection vehicles.

B. Genetic Algorithm for Route Optimization

The Genetic Algorithm is employed to optimize the routes for waste collection within each cluster. The Genetic Algorithm undergoes the following sequence of steps:

1. Initialization:  An initial population of routes is generated. Each route represents a sequence of waste collection points within a cluster, ensuring that each point is visited exactly once
2. Fitness Evaluation:  The fitness of each route is evaluated based on the total distance traveled. The distance matrix between waste collection points is computed using geographical coordinates. Lower total distances indicate fitter routes
3. Selection: The parent routes for the next generation are chosen based on their fitness level. This selection process employs a mechanism such as tournament selection or roulette wheel selection to identify the fittest individuals within the population.
4. Crossover: The crossover is applied to selected parent routes to generate offspring. The crossover point is selected randomly, and segments of routes beyond the crossover point are swapped between parents to create new routes.
5. Mutation: The mutation is introduced to maintain genetic diversity within the population. Randomly selected genes (waste collection points) in individual routes are swapped or altered with a certain probability.
6. Replacement: Here, the newly generated optimized routes through crossover and mutation are replaced by the least optimal routes. Such that this ensures that the most optimal routes are evolved over successive generations.
7. Termination: The algorithm terminates after a predefined number of generations or when a convergence criterion is met. The best-performing routes found during the optimization process are selected as the final solution.

C. Route Assignment to Vehicles

Once optimized routes are derived for every cluster, the routes need to be assigned to available waste collection vehicles while adhering to capacity constraints. The waste generation volume of each waste collection point is considered in this step. Points are assigned to vehicles based on their proximity to each other and the capacity of the vehicles. A vehicle's capacity is determined by the maximum volume of waste it can carry. The assignment process ensures that each vehicle's capacity is not exceeded, and waste collection points are efficiently distributed among vehicles.

IV. RESULTS AND DISCUSSIONS

In this section, the outcomes of the GreenRoute Ballari project are illustrated that are obtained by applying a combination of K-means clustering and Genetic algorithm to the waste collection input data points, we obtained optimized waste collection routes for various areas across Ballari City. The specific coordinate data used for mapping is simulated due to the unavailability of Ballari's precise data. The below figures present the visual representation of optimized routes for waste collection using MapBox

A. Route Optimization Results

Implementing K-means clustering and Genetic Algorithm yielded optimized waste collection routes tailored to the specific spatial distribution of waste generation points in the study area. Here are the key findings:

1. Reduced Travel Distances: The optimized routes significantly reduced the total travel distances compared to traditional static routes, resulting in more fuel-efficient and cost-effective waste collection operations.
2. Improved Operational Efficiency: By minimizing travel distances and optimizing stop sequences, the waste collection vehicles were able to complete their routes more efficiently, leading to reduced operational costs and increased productivity.
3. Dynamic Adaptation: Applying machine learning to predict the waste allowed the system to dynamically adapt to changing waste generation patterns, ensuring that the routes remained optimal and responsive to real-time conditions.

B. Mapping Results

Despite using coordinate data from Ballari for visualization purposes, the mapping of optimized routes using MapBox API provided insightful representations of the optimized waste collection routes. The map displayed:

1. Clustered Collection Points: The distinct clusters of waste collection points across Ballari City were represented by K-means clustering.
2. Optimized Routes: The optimized routes that are generated from the Genetic Algorithm are overlaid on the map, depicting the order of waste collection points within each cluster. These routes are optimized to minimize travel distances and adhere to capacity constraints.
3. Visualization of Efficiency Gains: Through the map interface, stakeholders could observe the spatial distribution of waste collection activities and the efficiency gains achieved through route optimization.

Conclusion

The effective management of municipal waste poses a significant challenge in the transformation of Ballari City towards eco-friendly and smart urban development. In this paper, we have proposed a system to optimize waste collection routes across Ballari City. In response to that, a combination of K-means clustering and genetic algorithms are used to obtain optimized routes using the waste collection points as input data. This approach aims to minimize travel distance, reduce fuel costs, and optimize time allocated for waste collection. The proposed system is beneficial for waste carrier truck drivers to prioritize the routes for waste collection. Additionally, the system benefits municipal authorities by enhancing resource deployment and planning. In conclusion, the system represents a significant step towards the sustainable development of Ballari City.

References

[1] S. Ahmad, Imran, F. Jamil, N. Iqbal, and D. Kim, “Optimal route recommendation for waste carrier vehicles for efficient waste collection: A step forward towards sustainable cities,” IEEE Access, vol. 8, 2021, doi: 10.1109/ACCESS.2021.2988173. [2] T. Parsons, J. Seo, and D. Livesey, \"Waste Collection Area Generation Using a 2 Stage Cluster Optimization Process and GIS Data,\" IEEE Access, vol. 11, pp. 11849-11859, 2023, doi: 10.1109/ACCESS.2023.3241626. [3] ?. Wojciechowski, T. Cisowski, and A. Ma?ek, “Route optimization for city cleaning vehicle,” Open Engineering, vol. 11, no. 1, 2021, doi: 10.1515/eng-2021-0049. [4] H. L. Vu, K. T. W. Ng, B. Fallah, A. Richter, and G. Kabir, “Interactions of residential waste composition and collection truck compartment design on GIS route optimization,” Waste Management, vol. 102, 2020, doi: 10.1016/j.wasman.2019.11.028. [5] N. L. Rachmawati, Y. A. Iskandar, D. P. Putri, and M. Lusiani, “A Genetic Algorithm Approach for Waste Collection Using Multi-trip Multi-period Capacitated Vehicle Routing Problem with Time Windows (MCVRPTW),” 2023. doi: 10.46254/an13.20230217.

Copyright

Copyright © 2024 Manasa Bellamkonda, Dinesh N, K Pravallika, Zaheed Hussain, Noorullah Shariff C. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.